package com.localking.algorithm.leetcode.array.matrix

/**
 * Given a non-negative integer numRows, generate the first numRows of Pascal's triangle
 * In Pascal'w triangle, each number is the sum of the tow number directly above it.
 *
 * Example:
 * Input: 5
 * Output:
 * [
 *        [1],
 *      [1, 1],
 *    [1, 2, 1],
 *  [1, 3, 3, 1],
 * [1, 4, 6, 4, 1]
 * ]
 *
 * @author jinbo
 */
object PascalTriangle_118 {

  def main(args: Array[String]): Unit = {
    generate(5).foreach(println(_))
  }

  def generate(numRows: Int): List[List[Int]] = {
    numRows match {
      case 0 => List.empty
      case 1 => List(List(1))
      case _ => {
        val previous: List[List[Int]] = generate(numRows - 1)
        val lastRow: List[Int] = previous.reverse.head
        var currentRow: List[Int] = List.empty
        var header = 0
        lastRow.foreach(x => {
          currentRow = (header + x) :: currentRow
          header = x
        })
        ((1 :: currentRow) :: previous.reverse).reverse
      }
    }
  }
}
